A computer system consists of one or more physical (or logical) central processing units, and software. The software consists of an operating system and applications. The operating system controls the hardware and enables various applications to execute.
A multitasking operating system allows multiple applications to execute seemingly simultaneously, by rapidly switching between multiple tasks.
The applications may consist of one or more execution units, called processes. Each of these processes may also consist of one or more thread units. A thread is the smallest execution context that may be scheduled for execution. A task is the generic term for a process or thread.
Typically, only one task may be actually executing instructions in a processor at a given time. In a multi-processor system, one task may be executing in each of the processor units at a time.
The multitasking operating systems include a schedule component responsible for the determination of which task will execute at any given time. A scheduling algorithm is used to make this determination.
The prior art task scheduling algorithms of conventional operating systems often consist of some combination of a task state, time allocation, priority, and length of time waiting for execution:                While systems may categorize tasks by a variety of states, for the purpose of scheduling, the states may be summarized as “currently executing:, “ready to execute”, or “not ready to execute”. A task in the currently executing state is one that is presently executing instructions in a processor. A task that is in the ready to execute state is one that is not presently executing instructions in a processor, however is able to do so at the next opportunity to do so. A task in the not ready to execute state is one that is not presently executing instructions in a processor, and should not be scheduled to do so because it has no work of value to perform at this time.        A time allocation is the maximum time that a task is allowed to continuously execute in a processor without allowing another task an opportunity to execute.        An overall priority for the task may be determined by a number of factors, including combinations of application, process, and/or thread based priority, and adjustments due to current conditions of the task.        
In conventional operating systems, an executing task may be suspended (temporarily set aside) for one of multiple causes, usually including:                The task itself requests execution suspension when it desires to allow other tasks to execute because it has finished with a desired action or is waiting for a resource (for example, access to a disk), communication, or input (user action).        The task scheduling may pre-empt and suspend a task due to a change of state of a higher priority suspended task.        The task scheduling may pre-empt and suspend a task due to a change of priority of another suspended task.        The task scheduling might pre-empt a task after a period of time.        
Suspension of a task involves the saving of its execution state and data structures, which may later be swapped back in to continue execution as if it were never suspended.
When a thread enters a “ready to execute state”, it is added to the end of a ready queue (possibly based on its priority). In a pre-emptive scheduler, this may cause the currently executing thread to be suspended.
In a conventional, multi-purpose operating system, when one or more tasks consume too many common resources (such as CPU cycles), other tasks may become “starved”, meaning they do not receive sufficient, or timely, execution. The effect of this is that the starved tasks may cause unacceptable feedback latency to users or in the extreme software may fail time-outs or crash. On systems supporting multiple users, such effects can limit the number of users that may perform useful work.
In the field of communications packet processing, a parallel set of issues exists. A device may process packets commutation streams from many sources. Often these streams compete with each other for use of a limited shared resource, such as bandwidth on a wide-area network link. If one stream uses too much of the shared resource, other streams may become starved, causing packet retransmissions, time-outs, or in the extreme application failures.
To overcome these issues in packet processing, Quality-of-Service (QoS) algorithms are sometimes used to schedule packets from multiple streams. A QoS based scheduling algorithm uses as input a set of quality parameters outlining ranges of acceptable (or desired) resource usage ranges for competing uses. By applying QoS metrics and algorithms to packet processing, these problems have been overcome in the packet-processing field.